「进阶0x3B」GCD

没完没了的sb数学题，推导一下就知道怎么切了

首先需要$gcd(x,y)$是一个质数，就是$gcd(x,y)=p$

$$\begin{cases} &x=x0\times p\\ &y=y0\times p \end{cases}$$

又因为$gcd(x,y)=p$，所以$gcd(x0,y0)=1$，这样的数的个数不就是$\phi [x]$个吗

然后求个和，可以得到最终答案就是$\sum_{i=1}^{n}\sum_{j|i}2\times \phi[i/j]-1$

这里乘二是因为$x，y$之间没有规定大小关系，可以是$(x,y)$或$(y,x)$，再减去$1$是删去$x==y$的情况多乘了一次二

但是这样的复杂度也才$O(nlog(n))$，还不足以通过本题

发现有很多重复计算的地方，思考一下，其实套个前缀和就可以$O(n)$解决了，就是直接统计所有满足条件的答案